package leetcode_700;

/**
 *@author 周杨
 *DecodeWaysII_639 通配符匹配 
 *describe:用动态规划 AC 8% 可以减少维度
 *2018年9月25日 上午10:08:41
 */
public class DecodeWaysII_639 {
	 int mod = 1000000007;
	public static void main(String[] args) {
		DecodeWaysII_639 test=new DecodeWaysII_639();
		System.out.println(test.numDecodings("1*23"));
	}
	
	 public int numDecodings(String s) {
	        if(s == null || s.length()== 0)
	            return 0;
	        
	        //M[i] represents the # of decoded combinations from index 0 to i
	        long[] M = new long[s.length()+1]; 
	        M[0] = 1;
	        //base case
	        //M[i], if i is valid single digit(not zero), then we can decode it M[i-1] ways
	        //if i and i-1 is valid double digit, then we can decode it M[i-2] ways
	        
	        //* case
	        //if i is * and we treat it as single digit, we can decode it 9 * M[i-1] ways
	        //if i is * and i-1 is either (1 or 2), if 1, then we  can decode it 9 * M[i-2] ways or 6 * M[i-2] ways
	        //if i is a number between 0 and 6 and i-1 is *, then we can decode it 2 * M[i-2] ways
	        //if 1 is a number between 7 and 9 and i-1 is *, then we can decode it 1 * M[i-2] ways
	        //if i is * and i-1 is *, then we can decode it 15 * M[i-2] ways
	        for(int i = 1; i <= s.length(); i++) {
	            if(s.charAt(i-1) == '*') {
	                M[i] += 9*M[i-1]; //treat as single digit
	                if(i >= 2) { //treat as double digit
	                    if(s.charAt(i-2) == '1')
	                        M[i] += 9 * M[i-2];
	                    else if(s.charAt(i-2) == '2')
	                        M[i] += 6 * M[i-2];
	                    else if(s.charAt(i-2) == '*')
	                        M[i] += 15 * M[i-2];
	                }
	            } else {
	                if(s.charAt(i-1) != '0') { //treat as single digit
	                    M[i] += M[i-1];
	                }
	                if(i >= 2) { //treat as double digit
	                    if(s.charAt(i-2) != '*' && Integer.parseInt(s.substring(i-2, i)) >= 10 && Integer.parseInt(s.substring(i-2, i)) <= 26)
	                        M[i] += M[i-2];
	                    else if(s.charAt(i-2) == '*' && Integer.parseInt(s.substring(i-1, i)) >= 0 && Integer.parseInt(s.substring(i-1, i)) <= 6)
	                        M[i] += 2*M[i-2];
	                    else if(s.charAt(i-2) == '*' && Integer.parseInt(s.substring(i-1, i)) >= 7 && Integer.parseInt(s.substring(i-1, i)) <= 9)
	                        M[i] += M[i-2];
	                }
	            }
	            M[i] = M[i] % 1000000007;
	        }
	        return (int)M[s.length()];
	    }
	
	/**
	 * describe:还未考虑到所有情况  如"*1*1*0"
	 * 2018年9月25日 上午10:07:22
	 */
	public int numDecodings1(String s) {
       if(s.length()==1)
    	   return "*".equals(s)?9:1;
       int dp0=1;
       char [] chars=s.toCharArray();
       int dp1=chars[0]=='*'?9:1;
       for(int i=1;i<chars.length;++i) {
    	   int now=0;
    	   if(chars[i]=='*') {
    		   now+=9*dp1;
    		   if(chars[i-1]=='*') {
    			   now+=dp0*15;
    		   }
    		   else if(chars[i-1]=='1') {
    			   now+=9*dp0;
    		   }
    		   else if(chars[i-1]=='2') {
    			   now+=6*dp0;
    		   }
    	   }
    	   else if(chars[i]<='6'){
    		   now+=dp1;
    		   if(chars[i-1]=='*') {
    			   now+=dp0*2;
    		   }
    		   else if(chars[i-1]<='2') {
    			   now+=dp0;
    		   }
    	   }
    	   else {
    		   now+=dp1;
    		   if(chars[i-1]=='*'||chars[i-1]=='1') {
    			   now+=dp0;
    		   }
    	   }
    	   dp0=dp1;
    	   dp1=now%mod;
       }
       return dp1;
    }
}
